package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * 2439. 最小化数组中的最大值
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/16 20:18
 */
public class MinimizeArrayValue {

    public static void main(String[] args) {
        MinimizeArrayValue test = new MinimizeArrayValue();

//        int[] arr = Utils.getArr(100, 1, 100000);

//        int[] arr = {3, 7, 1, 6};

        // 10
        int[] arr = {10,1};

        int i = test.minimizeArrayValue(arr);
        System.out.println(i);
    }

    public int minimizeArrayValue(int[] nums) {
        int length = nums.length;
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int max = 0;
        long item = 0;
        for (int i = length - 1; i >= 0; i--) {
            long a = nums[i] + item;
            int b = (int) ((sum + i) / (i + 1));
            if (a > b) {
                item = (a - b);
            } else {
                b = (int) a;
                item = 0;
            }
            sum -= b;
            max = Math.max(max, b);
        }
        return (int) Math.max(max, item);
    }

}
